

//class Solution {
//    public ListNode sortList(ListNode head) {
//        if (head == null || head.next == null) return head;
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode next = null;
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            if (fast == null || fast.next == null) next = slow;
//            slow = slow.next;
//        }
//        next.next = null;
//        ListNode left = sortList(head);
//        ListNode right = sortList(slow);
//        return mergeSort(left, right);
//    }
//
//    public ListNode mergeSort(ListNode l1, ListNode l2) {
//        ListNode dummy = new ListNode(-1);
//        ListNode cur = dummy;
//        while (l1 != null && l2 != null) {
//            if (l1.val <= l2.val) {
//                cur.next = l1;
//                l1 = l1.next;
//                cur = cur.next;
//            } else {
//                cur.next = l2;
//                l2 = l2.next;
//                cur = cur.next;
//            }
//        }
//        if (l1 != null) {
//            cur.next = l1;
//        }
//        if (l2 != null) {
//            cur.next = l2;
//        }
//        return dummy.next;
//    }
//}